﻿/// * Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia).


using System;

class zad13
{
    static void Main()
    {
        int[] arr = { 1, 3, 5, 2, 7 };
        int middle = arr.Length / 2;
        int[] res = MergeSort(arr);
        //Console.WriteLine();
    }

    public static int[] MergeSort(int[] arr)
    {
        int[] result = MergeSort(arr, 0, arr.Length - 1);
        return result;
    }

    public static int[] MergeSort(int[] input, int left, int right)
    {
        int[] result = new int[input.Length];

        if (left < right)
        {
            
            int middle = (left + right) / 2;

            MergeSort(input, left, middle);
            MergeSort(input, middle + 1, right);

            int[] leftArray = new int[middle - left + 1];
            int[] rightArray = new int[right - middle];

            Array.Copy(input, left, leftArray, 0, middle - left + 1);
            Array.Copy(input, middle + 1, rightArray, 0, right - middle);

            int i = 0;
            int j = 0;
            for (int k = left; k < right + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    result[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    result[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    result[k] = leftArray[i];
                    i++;
                }
                else
                {
                    result[k] = rightArray[j];
                    j++;
                }
            }

           
        }

        return result;
    }

}

